package com.company;

public class Main {

    public static void main(String[] args) {
	    int arr[]={2,1,3,323,55,332,13};
	    int n = arr.length;
	    quick_sort(arr,n);
	    print_arr(arr,n);
    }

    //辅助函数，打印数组
    static void print_arr(int arr[],int n)
    {
        for (int i=0;i<n;i++)
        {
            System.out.println(arr[i]);
        }
    }

    //辅助函数:交换变量值
    static void swap(int a,int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }

    //划分函数
    static int partition(int arr[],int low,int high)
    {
        int i = low-1;
        int j = high;
        int pivot = arr[high];
        while (true)
        {
            while (arr[++i]<pivot);
            while (arr[--j]>pivot);
            if(i<j)
            {
                swap(arr[i],arr[j]);
            }else
                break;
        }
        swap(arr[i],arr[high]);//arr[high]枢纽元素放到正确的位置
        return i;
    }


    //快速排序核心
    static void qsort(int arr[],int low,int high)
    {
       if(low<high)
       {
          int mid = partition(arr,low,high);//先找中间值再分左右
          qsort(arr,low,mid-1);
          qsort(arr,mid+1,high);
       }
    }

    //快速排序入口
    static  void quick_sort(int arr[],int n)
    {
        qsort(arr,0,n-1);//n-1从最后一个开始划分
    }

}
